/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年01月20日
*   描    述：
*   
================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int len = nums.size();
        int count1 = 0, count2 = 0;
        int nums1 = 0, nums2 = 0;
        vector<int> res;
        for( int i = 0; i < len; i++ ){
            if( nums1 == nums[i] ){
                count1++;
            }else if( nums2 == nums[i] ){
                count2++;
            }else if( count1 == 0 ){
                nums1 = nums[i];
                count1 = 1;
            }else if( count2 == 0 ){
                nums2 = nums[i];
                count2 = 1;
            }else{
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;
        for( int i = 0; i < len; i++ ){
            if( nums1 == nums[i] )
                count1++;
            else if( nums2 == nums[i] )
                count2++;
        }
        
        if( count1 > len/3 )
            res.push_back(nums1);
        if( count2 > len/3 )
            res.push_back(nums2);

        return res;
    }
};
